package sort;

import java.util.Arrays;

//希尔排序，时间复杂度 O(nlogn),80000个数据下 交换法 17s ； 移动法 1s。
public class shellSort {
	public static void main(String[] args) {
		int array[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
		shellSort2(array);
		System.out.println(Arrays.toString(array));
	}

	/*
	希尔排序时，对有序列在插入时有  交换法（效率低，易理解） 和 移动法（效率高，难理解）
	尽快把小的数提到前面，来减少排序时间
	 */
	public static void shellSort(int[] array) {
		//1.交换法
		//1.1 第一轮，将十个数分成 10/2=5 组，对每组的2个元素进行冒泡
		//1.2 第二轮，将十个数分成 5/2=2 组，对每组的4个元素进行冒泡
		//1.3 第三轮，将十个数分成 2/2=1 组对每组的10个元素进行冒泡
		int group = array.length;
		int temp = 0;
		while (group > 1) {
			group /= 2;
			for (int i = group; i < array.length; i++) {
				//遍历各组中的所有元素
				for (int j = i - group; j >= 0; j -= group) {
					//如果当前这个元素大于加上步长后的那个元素（同一组的元素）,说明交换
					if (array[j] > array[j + group]) {
						temp = array[j];
						array[j] = array[j + group];
						array[j + group] = temp;
					}
				}
			}

		}

	}

	//对 交换法 的希尔排序进行优化，改为移动法
	public static void shellSort2(int[] array) {
		int group = array.length;
		int temp = 0;
		while (group >= 1) {
			group /= 2;
			//从第 group 个元素开始，逐个对其所在的组进行插入排序
			for (int i = group; i < array.length; i++) {
				int j = i; //零时遍历，待插入的位置的下表
				temp = array[j];
				//找位置
				if (array[j] < array[j - group]) {
					while (j - group >= 0 && temp < array[j - group]) {
						//移动
						array[j] = array[j - group];
						j -= group;
					}
					//当退出循环，找到位置
					array[j] = temp;
				}

			}
		}
	}


}
